import Data.List

showRom :: Integer -> String
showRom = concat . unfoldr go
  where
    go 0 = Nothing
    go n | ((m,s):_) <- filter ((<=n) . fst) xdigits = Just (s,n-m)

    xdigits = reverse $ sort $
              [ (n,[d]) | (n,d) <- digits ] ++
              [ (n2-n1,[d1,d2]) | (n1,d1) <- digits, d1 `notElem` "VLD"
                                , (n2,d2) <- digits, n1 < n2
                                ]

    digits = [(1,'I'),(5,'V'),(10,'X'),(50,'L'),(100,'C'),(500,'D'),(1000,'M')]

int2Rom :: Integer -> String
int2Rom 0 = []
int2Rom i = int2Rom' i digits
  where
    int2Rom' i ((n,d):ds)
      | i >= n = d ++ int2Rom (i - n)
      | otherwise = int2Rom' i ds

    digits = [(1000,"M"),(999,"IM"),(990,"XM"),(900,"CM"),(500,"D"),(499,"ID")
             ,(490,"XD"),(400,"CD"),(100,"C"),(99,"IC"),(90,"XC"),(50,"L"),(49,"IL")
             ,(40,"XL"),(10,"X"),(9,"IX"),(5,"V"),(4,"IV"),(1,"I")]

-- benchmark purpose
main = do
  putStrLn . show $ map int2Rom [1..100000]
